home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Chip 1996 April
/
CHIP 1996 aprilis (CD06).zip
/
CHIP_CD06.ISO
/
hypertxt.arj
/
9511
/
LEPESKIV.CD
< prev
next >
Wrap
Text File
|
1996-03-10
|
14KB
|
237 lines
@VLépéskiválasztás logikai játékokban@N
@VHat gyalog@N
Logikai és táblás játékprogramok írásakor a legkeményebb
dió nem a tetszetôs kezelôfelület elkészítése, hanem egy
erôs számítógépes ellenfél programjának megírása.
Bár a mai gépek számítási kapacitása igen nagy, az
úgynevezett ""állapotrobbanás" miatt a legtöbb logikai
játékhoz nem lehet minden elôzetes meggondolás nélkül, a
""nyers erô" módszerével elfogadható szinten játszó
programot írni. îgy a számítógépes játékok elméletéhez is
nagy matematikai, algoritmuselméleti apparátus alakult ki.
E cikk ismerteti a játékok matematikai
reprezentációjának néhány módszerét, majd a legjobb lépés
kiválasztására szolgáló, általánosan elterjedt @Kminimax,@N
illetve @Kalfa-béta@N eljárást, de a konkrét megvalósítás,
kódolás kérdéseire nem tér ki. A módszerek alkalmazhatók
szinte minden olyan játékra, melyben két, egymással szemben
álló játékos (esetünkben az egyik mindig a számítógép)
rögzített szabályok szerint egy szintén jól definiált cél
(gyôztes helyzet) elérése érdekében felváltva ""lép". Egy
adott szituációban a választható lépések száma mindig véges.
A véletlen szerepe a játékokban nulla.
@VJátékok reprezentálása@N
A játékállás mindazon információk összessége, amelyek
egy játék menete során egy adott pillanatban az addig elért
szituációt leírják. A korábbi lépések az elkövetkezô
állásokat csak a pillanatnyi játékálláson keresztül
befolyásolhatják, így a pillanatnyi játékállás elegendô
információt tartalmaz a játékos számára a következô lépés
kiválasztásához. Például a sakkban a táblán lévô bábuk
elhelyezkedése és az, hogy lehet-e még sáncolni, valamint
hogy melyik oldal lép legközelebb, együtt adja a
játékállást. Kitüntetett szerepe van a kezdô és a befejezô
állásoknak. (Ezeket egyértelmûen meghatározzák a
játékszabályok.)
Ha a játékállások száma véges, a játék reprezentálható
az állapotdiagrammal. Ez egy olyan gráf, amelyben a
játékállások alkotják a csúcsokat, és a lehetséges lépések
irányított élek a régi állásból az újba.
Sok szempontból célszerûbb lehet a játékfa alkalmazása.
Ez abban különbözik az állapotdiagramtól, hogy ha ugyanaz a
játékállás többféle elôzménnyel is elérhetô, akkor mindnek
külön csúcsot veszünk fel. Belátható, hogy így gráfelméleti
értelemben fagráfot kapunk. Szokás a játékfa éleit lefelé
irányítani, így a kezdô állás, vagyis a gyökér (0. szint)
alatt az egy lépésben elérhetô állások szerepelnek (1.
szint), alatta a két lépésben elérhetô állások, és így
tovább. Ha a két játékos felváltva lép, akkor a fában is
váltják egymást a két játékos lépéslehetôségeinek megfelelô
szintek.
Ha nincs korlátozva a lépések száma, a fa akár végtelen
is lehet, bár az egy szinten elhelyezkedô csúcsok száma
mindig véges. Ha minden csúcsnak @Kk@N darab fia van (@Kk@N él indul
ki belôle), akkor az @Kn.@N szinten már @Kkⁿ@N darab csúcs van,
tehát az úgynevezett állapotrobbanás miatt a csúcsok száma
általában még véges esetben is olyan nagy, hogy a játékfának
csak egy részfája vizsgálható egyszerre.
@VA statikus állásértékelô függvény@N
Mint megállapítottuk, egy játékállásból egyszerûen
meghatározhatók az adott helyzetben lehetséges lépések, így
a játékfa könnyen felépíthetô. A legjobb lépés a
játékfa(-részlet) vizsgálatával választható ki. Ehhez
szükség lesz arra, hogy két állást ""jóság" (mennyire vannak
közel a gyôzelemhez) szempontjából össze tudjunk
hasonlítani. Az összehasonlításhoz az úgynevezett statikus
állásértékelô függvényt használjuk, ami egy tetszôleges
álláshoz egy számszerû értéket (""jóságot") rendel. Gyôztes
állás jósága plusz végtelen (vagy egy nagyon nagy szám),
vesztes állásé pedig mínusz végtelen.
Az értékelô függvény elôállítására nincsenek matematikai
módszerek. Åltalában a sok játékkal szerzett
tapasztalatainkat kell egyetlen formulába öntenünk.
Szem elôtt kell tartanunk, hogy programunk csak annyira
játszhat jól, amennyire reális az értékelô függvényünk.
Különösen nehéz a jó állásértékelô függvény megalkotása a
sakknál.
@VLépéskiválasztás minimax és alfa-béta eljárásokkal@N
Egy adott állás mellett a legjobb következô lépést az
alábbi minimax eljárással választhatjuk ki.
Ållítsuk elô az adott állásból az összes lehetséges
folytatás generálásával a játékfát @Kn@N szint mélységig
(feltételezve, hogy @Kn@N lépéssel gondolkodunk elôre). Ezután
állapítsuk meg a legalsó szinten lévô állások ""jóságát" a
statikus értékelô függvénnyel. Nevezzük el azokat a
csúcsokat, amelyek után az ellenfél jön @KVAGY@N csomópontoknak,
míg a többit @KÉS@N csomópontnak! (A játékfában a @KVAGY@N és az @KÉS@N
csúcsokat tartalmazó szintek felváltva következnek.)
Ésszerû feltételezés, hogy mindkét játékos mindig a
számára legjobb lépést választja. Ez számunkra a legnagyobb,
az ellenfél számára a legkisebb értékû állás. Ha tehát
például az @Kn-1.@N szinten mi lépünk (@KÉS@N szint), akkor minden,
az @Kn-1.@N szinten lévô csomópontnál a belôle elérhetô
állásokból a legnagyobb értékû csúcsot választjuk ki, és
ennek értékét ""felvisszük". îgy végigmenve a csomópontokon
már a teljes @Kn-1.@N szintet kiértékeljük. Ezután az @Kn-2.@N
szinten (@KVAGY@N szint) az ellenfél mindig a legkisebb értékû
fiú csomópontot választja, és ennek értékét viszi fel. Az
eljárást alulról felfelé haladva egészen a fa gyökeréig
végezzük. Végül az elsô szint legnagyobb értékû
csomópontjának megfelelô lépést tesszük meg.
Idônyerô észrevétel, hogy miután az ellenfél válaszolt
lépésünkre, az új lépés kiválasztásához már részben
rendelkezésre áll a játékfa, csupán egy szinttel lejjebb
kell menni. Természetesen a legjobb értékek felvitelét újra
el kell végezni, így csak a játékfa létrehozásán spóroltunk
valamennyit.
Ha a fa generálásakor egybôl kiértékeljük a
csomópontokat, a fa felesleges ágainak ""levágásával"
szintén sok idôt nyerhetünk. Ugyanis ha például egy olyan
szinten, ahol mi lépünk, plusz végtelen értékû csomópontot
találunk, akkor ennek közvetlen szomszédaival és azok
leszármazottaival nem kell foglalkoznunk, hiszen a
gyôzelemnél (plusz végtelen érték) jobb folytatás nem
képzelhetô el. (Ugyanez a helyzet az ellenfél lépéseinél a
mínusz végtelennel.)
@VAz alfa-béta eljárás@N
Hasonló megtakarítás nemcsak közvetlen nyerési lehetôség
esetén érhetô el. Ezen alapszik az úgynevezett alfa-béta
eljárás, mely a minimax módszer továbbfejlesztésének
tekinthetô.
A játékfát mélység szerinti bejárással generáljuk. Ez
azt jelenti, hogy egy csomópont leszármazottainak
bejárásakor sorban bejárjuk a fiait (rekurzió) úgy, hogy egy
új fiúra csak akkor térünk rá, ha az elôzô bejárása már
teljesen befejezôdött.
Ha végponthoz érünk (legalsó szint), akkor rögtön
elvégezzük a statikus értékelést, és a minimax szabállyal
kiválasztott értéket azonnal felvisszük a felette lévô
szintre. Ezt az értéket a fában a gyökértôl idáig bejárt út
mentén ideiglenesen felvisszük a felsôbb szintekre is. A
fenti értékek azért ideiglenesek, mert a még be nem járt
ágak módosíthatják ôket. Ez a módosítás azonban csak
javíthatja az értékeket, így az olyan farészletekkel, melyek
már biztosan nem javítanak, nem kell foglalkoznunk.
Ezek alapján az egyszerûsítés szabályai:
@V*@N A keresést nem kell elvégezni az olyan @KVAGY@N
csomópontok alatt, melyeknél a kiértékelés eredménye kisebb
vagy egyenlô az ôket megelôzô @KÉS@N csomópontok bármelyikének
ideiglenes értékénél. (Ezt alfa levágásnak nevezik, míg az
@KÉS@N pontok ideiglenesen felvitt értékei az alfa értékek.)
@V*@N A keresést szükségtelen folytatni minden olyan @KÉS@N
csomópont alatt, amelynél a kiértékelés eredménye nagyobb
vagy egyenlô bármely ôt megelôzô @KVAGY@N csomópont értékénél.
(Béta levágás, illetve béta érték.)
Természetesen az alfa-béta eljárás ugyanazt a lépést
választja ki, mint a minimax, de a keresési idô jóval
rövidebb.
@KTóth Bálint (s4078tot@@sun10.vsz.bme.hu vagy
@Kbali@@frey.inf.bme.hu)
@VPélda tik-tak-tóra@N
A tik-tak-tó játéknál, amely a jól ismert amôba 3*3-as
táblára korlátozott, egyszerûsített változata, egy
lehetséges @Ke(p)@N értékelô függvény lehet a következô:
@V*@N Ha @Kp@N nem gyôztes állás, akkor e(p) = a számunkra
szabad teljes sorok, oszlopok és átlók száma, mínusz ugyanez
az ellenfél számára.
@V*@N Ha @Kp@N állásnál mi nyerünk, akkor e(p) = plusz végtelen.
@V*@N Ha @Kp@N állásnál az ellenfél nyer, akkor e(p) = mínusz
végtelen.
@V""Tanulás"@N
A hagyományos algoritmusokkal -- amelyek közé a minimax
is tartozik -- (rögzített lépésmélységet véve) fix
játékerejû programot írhatunk. Érdekes lehetôség azonban, ha
programunk a lejátszott mérkôzések alapján változtatja
játékát, azaz tanul.
Vizsgáljuk meg ezt egy nagyon egyszerû játék, a
hatgyalog kapcsán. Egy 3*3-as táblán kezdetben az alsó
sorban 3 világos, a felsôben 3 sötét bábu van. Felváltva
lépnek a sakkbeli gyalog mozgása szerint (en passant lépés
nincs). Egy játékos akkor gyôz, ha egy gyalogot bevisz a
szemközti oldalra, ha az ellenfél minden bábuja elfogyott,
vagy ha az ellenfél nem tud lépni.
Legyen a számítógép a sötét (nem ô kezd). A játékot
elemezve kiderül, hogy mindössze 24 különbözô olyan
játékállás van, ahol ô jön, mindegyik állásnál 1--4
lehetséges lépéssel. Képzeljünk el a 24 állásnak megfelelôen
24 dobozt, minden dobozban a lehetséges lépéseknek
megfelelôen színes golyókat. (A különbözô lehetséges
lépésekhez különbözô színeket rendelünk.) A gép úgy játszik,
hogy az adott állásnak megfelelô dobozból véletlenszerûen
kiválaszt egy golyót, és a színének megfelelôen lép.
Semmiféle stratégiája nincs tehát, véletlenül nyer vagy
veszít. Azonban tanulhat a korábbi mérkôzésekbôl, ha vereség
esetén a következô játszma elôtt a ""rossz" lépések golyóit
nem teszi vissza, gyôzelem esetén pedig esetleg több azonos
golyót tesz a korábbi egy helyett. îgy hosszabb
mérkôzéssorozat után a dobozokban a jó lépéseknek megfelelô
golyók maradnak túlsúlyban, vagyis a program játékereje nô.
A golyók természetesen csak szemléltetésként
szerepelnek. A valóságban az egyes lépések kiválasztásának
valószínûségét módosítjuk a tapasztalataink alapján.
A módszer bonyolultabb játékokban való felhasználását
megnehezíti, hogy az állás+lépés kombinációk száma
kezelhetetlenül nagy lehet, de még ha a memóriakapacitás nem
akadály, akkor is a kombinációk számának növekedtével egyre
hosszabb mérkôzéssorozat kell egy elfogadható
valószínûség-eloszlás eléréséhez.
Érdekes észrevétel, hogy ha a gép nem egy tökéletes
játékossal, hanem egyéni stílust képviselô ellenféllel
játszik -- márpedig az emberi játékosok mind ilyenek --,
akkor a gép játékstílusa az ellenfeléhez idomul. îgy ha
hirtelen egy más stílust követô ellenfelet adunk neki, akkor
az addig tanult lépés-valószínûségek alapján esetleg gyengén
játszik. Kis idô elteltével azonban a gép ""átszokik" az új
ellenfélre.
@<9511\6GYALOG.GIF>■■@N 6 gyalog
@VAjánlott irodalom@N
Csákány Antal -- dr. Vajda Ferenc: Játékok
számítógéppel. Mûszaki könyvkiadó, 1980
N. J. Nilsson: Problem-solving methods in artificial
intelligence. McGraw-Hill Book Co., 1971